package com.clstu.leetcode;

import java.util.*;

public class Solution11 {

    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        System.out.println(networkDelayTime(times,4,2));

    }

    public static int networkDelayTime(int[][] times, int n, int k) {

        Graph graph = Graph.creatGraph(times,n);
        HashSet<Node> sure = new HashSet<>();
        HashMap<Node,Integer> disMap = new HashMap<>();
        disMap.put(graph.nodes.get(k-1) , 0);

        //DijsKra 算法
        int maxDis = 0;
        int i = 0;
        while(true){
            //如果遍历结束(图不连通肯遍历不完.)

            if(sure.size() == n){
                break;
            }

            //找到一个最近的点确定
            int minDis = Integer.MAX_VALUE;
            Node minNode = null;
            for(Map.Entry<Node,Integer> e : disMap.entrySet()){
                Integer dis = e.getValue();
                Node node = e.getKey();
                System.out.println("sure:"+sure+" node="+node+sure.contains(node));
                if(dis < minDis && !sure.contains(node)){
                    minDis = dis;
                    minNode = node;
                }
            }

            if(minNode != null){
                maxDis = Math.max(maxDis,disMap.get(minNode));
                sure.add(minNode);
                for(Edge e:minNode.connectedEdges){
                    if(!disMap.containsKey(e.to)){
                        disMap.put(e.to,minDis+e.weight);
                    }else{
                        disMap.put(e.to , Math.min( disMap.get(e.to),minDis+e.weight) );
                    }
                }
            }
            System.out.println("sure.size() = "+sure.size() + "      minNode = "+minNode + "  minNode.nexts"+minNode.nexts);
        }
        //图是否整个联通
        if(sure.size() == n){
            return maxDis;
        }else{
            return -1;
        }
    }


    //图类
    public static class Graph{
        List<Node> nodes = null;
        List<Edge> edges = null;

        public Graph(List<Node> ns,List<Edge> es){
            nodes = ns;
            edges = es;
        }

        //根据传入的数组创建图返回
        public static Graph creatGraph(int[][] arr,int n){
            //创建节点
            List<Node> nodes = new ArrayList<>();
            for(int i=1;i<=n;i++){
                nodes.add(new Node(i));
            }

            //连接图
            List<Edge> edges = new ArrayList<>();
            for(int i=0;i<arr.length;i++){
                Node from = nodes.get(arr[i][0]-1);
                Node to = nodes.get(arr[i][1]-1);
                int weight = arr[i][2];

                Edge edge = new Edge(from,to,weight);
                edges.add(edge);

                from.nexts.add(to);
                from.connectedEdges.add(edge);
            }

            return new Graph(nodes,edges);
        }
    }

    //点类
    public static class Node{
        public int id;
        public List<Edge> connectedEdges = new ArrayList<>();
        public List<Node> nexts = new ArrayList<>();

        public Node(int id){
            this.id = id;
        }

        public String toString(){
            return "Node:"+id;
        }
    }
    //边类
    public static class Edge{
        public Node from;
        public Node to;
        public int weight;

        public Edge(Node f,Node t,int w){
            from = f;
            to = t;
            weight =w;
        }
    }

}
class Solutionx {
    public static void main(String[] args) {
        System.out.println(strStr("a","a"));
    }
    public static int strStr(String haystack, String needle) {
        return KMP(haystack,needle);
    }

    //KMP算法
    public static int KMP(String str1, String str2){
        if(str1.length() < str2.length()){
            return -1;
        }
        //得到数组
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int[] pArr = getMaxPLArr(str2);
        System.out.println(Arrays.toString(pArr));
        int i = 0;
        int x = 0;
        while(true){
            //如果到最后
            if(i > str1.length()-str2.length()){
                break;
            }
            //如果找到了
            System.out.println("x="+x);
            if(x == s2.length){
                return i;
            }
            if(s1[i+x] == s2[x]){
                x++;
            }else if(x==0){
                //向前推不了了
                i++;
            }else{
                //向前推
                i = i+x-pArr[x];
                x = pArr[x];
            }
        }
        //没有找到才可能走到这里
        return -1;
    }

    //编写方法得到最长前后缀数组
    public static int[] getMaxPLArr(String s){
        if(s.length() == 1){
            return new int[]{-1};
        }
        char[] chars = s.toCharArray();
        int[] pArr = new int[s.length()];
        pArr[0] = -1;
        pArr[1] = 0;
        int cn = 0;
        for(int i=2;i<pArr.length;i++){
            while(true){
                //如果接着相等
                if(chars[i-1] == chars[cn]){
                    pArr[i] = ++cn;
                    break;
                }else if(cn == 0){
                    pArr[i] = 0;
                    break;
                }else{
                    //向前跳
                    cn = pArr[cn];
                }
            }
        }
        return pArr;
    }
}

class SolutionY {
    public static int countSpecialNumbers(int n) {
        //如果只有一位,不用判断直接返回
        if(n<10){
            return n;
        }
        //有点类似于N皇后回溯问题
        int len = (n+"").length();
        return setNum(0,len,n,0)-1;
    }

    //摆放第n位上的数
    public static int setNum(int n, int len, int max, int cur){
        //如果能来到最后一位,说明找到一个数
        if(n == len){
            if(isRepeted(cur)){
                return 0;
            }else{
                return 1;
            }
        }
        int N = 1;
        for(int i=0;i<n;i++){
            N*=10;
        }
        int res = 0;
        //回溯
        for(int i=0;i<10;i++){
            if(isValied(N*i+cur,max)){
                res+=setNum(n+1,len,max,N*i+cur);
            }
        }
        return res;
    }

    //编写方法判断第n位是否合法
    public static boolean isValied(int cur, int max){
        if(cur > max){
            return false;
        }
        //得到第n位的数
        int x = cur;
        while(x>=10){
            x = x/10;
        }
        //判断
        while(cur>=10){
            int last = cur%10;
            if(last == x){
                return false;
            }
            cur = cur/10;
        }
        return true;
    }

    //编写方法判别一个数上是否有重复位
    public static boolean isRepeted(int cur){
        String str = cur+"";
        char[] s = str.toCharArray();
        Arrays.sort(s);
        for(int i=1;i<s.length;i++){
            if(s[i] == s[i-1]){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(countSpecialNumbers(123456789));
        long end = System.currentTimeMillis();
        System.out.println("耗时:"+(end-start)+"ms");
    }
}